package datastructure.unionfind;

/**
 * 并查集实现，主要支持两个操作：并union和查isConnected，是否是一个集合
 * 特点：不考虑添加或者删除元素，着重处理对当前的元素集的操作
 */
public class UnionFind1 implements UF {
    private int[] id;

    /**
     * 初始化并查集，计算大小
     *
     * @param size
     */
    public UnionFind1(int size) {
        id = new int[size];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    @Override
    public int getSize() {
        return id.length;
    }

    @Override
    public boolean isConnect(int p, int q) {
        return find(p) == find(q);// 看在集合id中，p和q对应的编号是否一致
    }

    // union的时间复杂度是o(n)
    @Override
    public void unionElements(int p, int q) {
        int pId = find(p);
        int qId = find(q);
        //条件1，如果已经相连，直接返回
        if (pId == qId) {
            return;
        }
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pId) {
                id[i] = qId;
            }
        }
    }

    // 查找元素p对应的元素，时间复杂度O(1)
    private int find(int p) {
        if (p < 0 || p > id.length) {
            return -1;
        } else {
            return id[p];
        }
    }
}
